package lc.q51_100;

import java.time.OffsetDateTime;

public class Q79 {

    public boolean exist(char[][] board, String word) {
        int h = board.length;
        int w = board[0].length;
        boolean[][] checked = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean check = check(board, word, i, j, 0, checked);
                if (check) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean check(char[][] board, String word, int i, int j, int k, boolean[][] checked) {
        if (board[i][j] != word.charAt(k)) {
            return false;
        } else if (k == word.length() - 1) {
            return true;
        }
        checked[i][j] = true;
        int[][] direction = new int[][] {
                new int[]{0, 1},
                new int[]{0, -1},
                new int[]{1, 0},
                new int[]{-1, 0}
        };
        boolean result = false;
        for (int[] ints : direction) {
            int newI = i + ints[0];
            int newJ = j + ints[1];
            if (newI >= 0  && newI < board.length && newJ >= 0 && newJ < board[0].length) {
                if (!checked[newI][newJ]) {
                    boolean check = check(board, word, newI, newJ, k + 1, checked);
                    if (check) {
                        result = true;
                        break;
                    }
                }
            }

        }
        // 设置可以被回溯
        checked[i][j] = false;
        return result;
    }

}
